package com.xiaoyu.sort.basic;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 堆排序,是选择排序的一种改进算法
 *
 * 堆:一颗完全二叉树,符合从上到下,从左到右的顺序存储
 * 它可以转换成一个一维数组
 *
 * 转换后,有公式:
 *  对于任意一个结点i
 *  1.它的父节点的位置是:(i-1)/2
 *  2.它的左孩子结点的位置是:2*i+1
 *  3.它的右孩子结点的位置是:2*i+2
 *
 *
 * 简单来说:
 * 如果你要的是升序:那么使用大顶堆-->每次都将最大的元素(大顶堆的根结点)与最后一个叶子结点交换,
 * 然后将该结点排除下一次循环,这样就获取了一个最大值(即每次都获取最大值)
 * 1,2,3,4,5,6,7
 *
 * 如果你要的是降序:那么使用小顶堆-->每次都将最小的元素(小顶堆的根结点)与最后一个叶子结点交换,
 * 然后将该结点排除下一次循环,这样就获取了一个最小值(即每次都获取最小值)
 * 7,6,5,4,3,2,1
 *
 *
 *
 * @author: YuWenYi
 * @create: 2021-05-09 10:38
 **/
public class HeapSort {

    public static void heapSort(int[] tree){
        //先构建一个大顶堆
        build_heap(tree,tree.length);

        int temp;
        for (int i = tree.length-1; i >= 0; i--) {
            //进入for循环后交换首尾位置,然后将尾部隐藏
            temp = tree[i];
            tree[i] = tree[0];
            tree[0] = temp;
            //然后将剩余的被打乱的树重新堆化
            heapify2(tree,i,0);
        }
    }

    //自底向上的将整个tree进行堆化
    public static void build_heap(int[] tree,int len){
        //最后一个结点即为数组的最后一个数字
        int last_node = len-1;
        //由公式每一个结点的父节点为(i-1)/2,因此最后一个结点的父节点是(last_node-1)/2
        int parent = (last_node-1)/2;

        //按顺序自底向上的将每一个非叶子结点都变成堆,i>=0里面的等于很重要
        for (int i = parent; i >= 0; i--) {
            heapify2(tree,len,i);
        }
    }

    //算法一:递归写法
    public static void heapify(int[] tree, int len, int i) {//i代表着第i个非叶子结点
        if (i >= len){
            return;
        }
        int leftChild = 2*i+1;
        int rightChild = 2*i+2;
        int max = i;
        //leftChild < len的意义是:如果该非叶子结点没有右孩子,那么就没必要去比较了
        if (leftChild < len && tree[leftChild] > tree[max]){
            max = leftChild;
        }
        if (rightChild < len && tree[rightChild] > tree[max]){
            max = rightChild;
        }
        //如果max被改变过,就交换父节点和较大结点的位置
        if (max != i){
            int temp = tree[i];
            tree[i] = tree[max];
            tree[max] = temp;
            //由于交换后,如果该孩子结点也是非叶子结点,那么可能就会打乱其堆的结构,因此需要递归的将该堆结构恢复
            heapify(tree,len,max);
        }
    }

    //算法二:非递归循环写法
    public static void heapify2(int[] arr, int len, int i) {
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<len;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<len && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换)然后继续循环处理子节点
                arr[i] = arr[k];
                i = k;
            }else{   //因为本身就是需要先构建一个大顶堆,然后再在这个基础上处理数据
                     // 所以如果是小于就说明不需要调整,那么退出循环即可
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }


    public static void main(String[] args) {
        int[] arr = new int[]{-9,2,7,4,6,-20,8,-16,5,4,15};
        int[] nums = new int[]{0,1,4,2,3,4};
        int[] tree = new int[]{4,10,3,5,1,2};

        heapSort(arr);
        System.out.println(Arrays.toString(arr));

        //速率测试
//        int[] bigData = new int[8000000];
//        for (int i = 0; i < 8000000; i++) {
//            bigData[i] = (int)(Math.random() * 8000000);
//        }
//        long start = System.currentTimeMillis();
//        heapSort(bigData, bigData.length);
//        long stop = System.currentTimeMillis();
//
//        System.out.println((stop-start)/1000.0); //800万数据在2.7秒左右

    }
}
